package offer

import (
	"GoLeetcode/unionFindTag/unionFind"
)

/*
时间复杂度:O(N+M) 遍历邻接表(graph[i]表示与i相邻的节点) N表示节点的个数,M表示边数
空间复杂度:O(N) 存储并查集元素

bipartite 	美[baɪˈpɑːrtaɪt]  由两部分组成的

f1:并查集-用于解决图的连通性问题

并查集：用于解决连通性问题;判断两个元素是否在同一个集合中;将元素合并到同一个集合
合并：将元素合并到一个集合中，或将一个集合合并到另一个集合
查询：查询元素所在集合的代表元素（根节点）

二分图,即能否将所有节点分成两个集合,使得每一条边相邻的两个节点,分别来自不同的集合

A-B-C-A 例如A B C三个节点之间均有一条边相连,则无法构成二分图

思路:对于节点A,与节点A相邻的所有节点放到同一个集合X, 如果遍历其他节点B时发现B与B的相邻节点C在同一个集合,则无法分成二分图
*/

func isBipartite(graph [][]int) bool {
	uf := new(unionFind.UnionFind2)
	uf.Init(len(graph))
	for i, raw := range graph {
		for _, v := range raw {
			if uf.Find(v) == uf.Find(i) {
				return false
			}
			uf.Merge(raw[0], v)
		}
	}
	return true
}

/*
时间复杂度:O(N+M) N表示节点个数,M表示边数 (对N个节点进行dfs,每个节点只遍历其邻接边,所有N个节点总共遍历总边数M)
空间复杂度:O(N) 存储节点颜色的数组

双色标记法-未访问的为0,访问的为1,1的相邻节点为2,2的相邻节点为1
*/

var (
	RED       = 1
	GREEN     = 2
	UNCOLORED = 0
	colors    []int
	valid     bool
)

func isBipartite1(graph [][]int) bool {
	n := len(graph)
	colors = make([]int, n)
	valid = true

	for i := 0; i < n && valid; i++ {
		if colors[i] == UNCOLORED {
			dfs(graph, i, RED)
		}
	}
	return valid
}

func dfs(graph [][]int, node, color int) {
	colors[node] = color
	otherColor := RED
	if color == RED {
		otherColor = GREEN
	}
	for _, v := range graph[node] {
		if colors[v] == UNCOLORED {
			dfs(graph, v, otherColor)
			if !valid {
				return
			}
		} else if color == colors[v] {
			valid = false
			return
		}
	}
	return
}